package com.example.tree;

/**
 * Created by Quincy on 2018/9/12.
 * 输入一棵二叉树，求该树的深度。
 * 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
 */
public class TreeDepth {
    public class TreeNode{
        int val;
        TreeNode left = null;
        TreeNode right = null;
        TreeNode(int val){
            this.val = val;
        }
    }

    /**
     * 求最大深度
     * 如果二叉树为空，则深度为0
     * 如果不为空，分别求左子树的深度和右子树的深度，取最大的再加1。
     * */
    public int TreeDepth(TreeNode root) {
        if (root == null) return 0;

        int leftDepth = TreeDepth(root.left) + 1;
        int rightDepth = TreeDepth(root.right) + 1;
        return Math.max(leftDepth, rightDepth);

    }

    /**
     * 求最小深度
     * */
    public int MinDepth(TreeNode root){
        if (root == null) return 0;

        //判断左子树或右子树是否为空
        //若左子树为空，则返回右子树的深度，反之返回左子树的深度
        if (root.left == null) return MinDepth(root.right) + 1;
        if (root.right == null) return MinDepth(root.left) + 1;

        //如果都不为空，则返回左子树和右子树深度的最小值
        int leftDepth = MinDepth(root.left) + 1;
        int rightDepth = MinDepth(root.right) + 1;
        return Math.min(leftDepth, rightDepth);
    }
}
